package com.smh;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author shiminghui
 * @date 2025/3/7 16:19
 * @description: TODO
 */

public class _038_HashTable_test {

    @Test
    public void test() {
        System.out.println(lengthOfLongestSubstring("abba"));
        System.out.println(lengthOfLongestSubstring2("abba"));
    }

    /**
     * 找到两个相同元素的下标
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int anotherNum = target - nums[i];
            if (hashMap.containsKey(anotherNum)) {
                return new int[]{hashMap.get(anotherNum), i};
            } else {
                hashMap.put(nums[i], i);
            }
        }
        return null;
    }

    /**
     * 找到最长不重复子串的长度
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        char[] charArray = s.toCharArray();
        if (charArray.length == 0) {
            return 0;
        }
        HashMap<Character, Integer> hashMap = new HashMap<>();
        int begin = 0;
        int maxLength = 0;
        for (int i = 0; i < charArray.length; i++) {
            Integer index = hashMap.get(charArray[i]);
            if (index != null && index >= begin) {
                maxLength = Math.max(maxLength, i - begin);
                begin = index + 1;
            }
            hashMap.put(charArray[i], i);
        }
        return Math.max(maxLength, charArray.length - begin);
    }

    public int lengthOfLongestSubstring2(String s) {
        char[] charArray = s.toCharArray();
        int[] chars = new int[128];
        Arrays.fill(chars, -1);
        int begin = 0;
        int maxLength = 0;
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
            int index = chars[c]; //
            begin = index >= begin ? index + 1 : begin;
            maxLength = Math.max(maxLength, i - begin + 1);
            chars[c] = i;
        }
        return maxLength;
    }

    /**
     * 找出所有字符串的异位词
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hashMap = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String key = new String(charArray);
            List<String> list = hashMap.computeIfAbsent(key, k -> new ArrayList<>()); // 如果key不存在，则创建一个list，如果存在，则返回这个list
            list.add(str);
        }
        return new ArrayList<>(hashMap.values());
    }

    public List<List<String>> groupAnagrams2(String[] strs) {
        HashMap<ArrayKey, List<String>> hashMap = new HashMap<>();
        for (String str : strs) {
            ArrayKey arrayKey = new ArrayKey(str);
            List<String> list = hashMap.computeIfAbsent(arrayKey, k -> new ArrayList<>());
            list.add(str);
        }
        return new ArrayList<>(hashMap.values());
    }

    /**
     * 判断是否有重复
     * @param nums
     * @return
     */
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) {
                return true;
            }
            set.add(num);
        }
        return false;
    }

    /**
     * 寻找只出现一次的数字
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) { // 1 1 2 2
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; ) {
            if (nums[i] != nums[i - 1]) {
                return nums[i - 1];
            }
            i = i + 2;
        }
        return nums[nums.length - 1];
    }

    public int singleNumber2(int[] nums) { // 1 1 2 2
        int res = 0;
        for (int num : nums) {
            res = res ^ num;
        }
        return res;
    }

    /**
     * 判断是否是异位词
     *
     * @param s
     * @param t
     * @return
     */
    private boolean isAnagram(String s, String t) {
        char[] charArray = s.toCharArray();
        Arrays.sort(charArray);
        char[] charArray2 = t.toCharArray();
        Arrays.sort(charArray2);
        return Arrays.equals(charArray, charArray2);
    }

    private boolean isAnagram2(String s, String t) {
        // 创建一个26长度的数组，记录s中每个字母出现的次数
        int[] array = new int[26];
        for (char c : s.toCharArray()) {
            array[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
            array[c - 'a']--;
        }
        for (int i : array) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 获取第一个不重复的字符
     */
    private int firstUniqChar(String s) {
        int[] array = new int[26];
        char[] charArray = s.toCharArray();
        for (char c : charArray) {
            array[c - 'a']++;
        }
        for (int i = 0; i < charArray.length; i++) {
            if (array[charArray[i] - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 找到句子中出现个数最多的单词
     */
    private String mostCommonWord(String paragraph, String[] banned) {
        paragraph = paragraph.toLowerCase();
        // 按空格和, .!?等符号进行分割
//        String[] split = paragraph.split("[ ,.!?']");
        char[] charArray = paragraph.toCharArray();
        HashMap<String, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        for (char c : charArray) {
            if (c >= 'a' && c <= 'z') {
                sb.append(c);
            } else {
                if (!sb.isEmpty()) {
                    String key = sb.toString();
                    map.compute(key, (k, v) -> v == null ? 1 : v + 1);
                    sb.setLength(0); // 清空StringBuilder
                }
            }
        }
        if (!sb.isEmpty()) {
            map.compute(sb.toString(), (k, v) -> v == null ? 1 : v + 1);
        }


        ArrayList<String> list = new ArrayList<>();
        // 遍历map，找到出现次数最多的单词,并收集到list,过滤分隔符
        map.entrySet().stream().filter(e -> !e.getKey().isEmpty() && !Set.of(banned).contains(e.getKey())).max(Comparator.comparingInt(Map.Entry::getValue)).ifPresent(e -> list.add(e.getKey()));
        return list.get(0);
    }

    @Test
    public void test1() {
        String s = mostCommonWord("i am super star, but am man.", new String[]{"star"});
        System.out.println(s);
    }




    private static class ArrayKey {
        private int[] array = new int[26];

        public ArrayKey(String str) {
            char[] charArray = str.toCharArray();
            for (char c : charArray) {
                array[c - 'a']++;
            }
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof ArrayKey) {
                return Arrays.equals(array, ((ArrayKey) o).array);
            }
            return false;
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(array);
        }
    }

}
